package com.squirrel.michale;

import java.util.*;

/**
 * @author guanhao 观浩
 * @version 1.0.0.0
 * @createTime 2023/2/6 10:02 AM
 * @company Michale Squirrel
 * @link
 * @description
 *
 * 有一个具有 n 个顶点的 双向 图，其中每个顶点标记从 0 到 n - 1（包含 0 和 n - 1）。图中的边用一个二维整数数组 edges 表示，其中 edges[i] = [ui, vi] 表示顶点 ui 和顶点 vi 之间的双向边。 每个顶点对由 最多一条 边连接，并且没有顶点存在与自身相连的边。
 *
 * 请你确定是否存在从顶点 source 开始，到顶点 destination 结束的 有效路径 。
 *
 * 给你数组 edges 和整数 n、source 和 destination，如果从 source 到 destination 存在 有效路径 ，则返回 true，否则返回 false 。
 */
public class LeetCode1971_2 {

    public boolean validPath(int n, int[][] edges, int source, int destination) {
        List<Integer>[] adj = new List[n];
        for (int i = 0; i < n; i++) {
            adj[i] = new ArrayList<Integer>();
        }
        for (int[] edge : edges) {
            int x = edge[0], y = edge[1];
            adj[x].add(y);
            adj[y].add(x);
        }
        Queue<Integer> queue = new LinkedList<>();
        HashSet<Integer> set = new HashSet<>();
        queue.add(source);
        set.add(source);
        while (!queue.isEmpty()) {
            Integer poll = queue.poll();
            for (int i = 0; i < adj[poll].size(); i++) {
                Integer next = adj[poll].get(i);
                if (!set.contains(next)) {
                    set.add(next);
                    queue.add(next);
                }
            }
        }
        return set.contains(destination);
    }

    public boolean validPath2(int n, int[][] edges, int source, int destination) {
        List<Integer>[] adj = new List[n];
        for (int i = 0; i < n; i++) {
            adj[i] = new ArrayList<Integer>();
        }
        for (int[] edge : edges) {
            int x = edge[0], y = edge[1];
            adj[x].add(y);
            adj[y].add(x);
        }

        Queue<Integer> quene = new LinkedList<>();
        HashSet<Integer> set = new HashSet<>();

        quene.add(source);
        set.add(source);
        while (!quene.isEmpty()) {
            Integer poll = quene.poll();
            System.out.println(poll.toString());
            int node = poll.intValue();
            for (int i = 0; i < adj[node].size(); i++) {
                Integer next = adj[node].get(i);
                if (!set.contains(next)) {
                    set.add(next);
                    quene.add(next);
                }
            }
        }
        return set.contains(destination);

    }


    public boolean validPath3(int n, int[][] edges, int source, int destination) {
        List<Integer>[] adj = new List[n];
        for (int i = 0; i < n; i++) {
            adj[i] = new ArrayList<Integer>();
        }
        for (int[] edge : edges) {
            int x = edge[0], y = edge[1];
            adj[x].add(y);
            adj[y].add(x);
        }
        Stack<Integer> stack = new Stack<>();
        HashSet<Integer> set = new HashSet<>();
        stack.add(source);
        set.add(source);
        while (!stack.isEmpty()) {
            Integer poll = stack.pop();
            for (int i = 0; i < adj[poll].size(); i++) {
                Integer next = adj[poll].get(i);
                if (!set.contains(next)) {
                    set.add(next);
                    stack.push(next);
                }
            }
        }
        return set.contains(destination);
    }

    public  void bfs(int n, int[][] edges) {
        List<Integer>[] adj = new List[n];
        for (int i = 0; i < n; i++) {
            adj[i] = new ArrayList<Integer>();
        }
        for (int[] edge : edges) {
            int x = edge[0], y = edge[1];
            adj[x].add(y);
            adj[y].add(x);
        }

        if (n == 0) {
            return;
        }

        Queue<Integer> quene = new LinkedList<>();
        HashSet<Integer> set = new HashSet<>();

        quene.add(0);
        set.add(0);
        while (!quene.isEmpty()) {
            Integer poll = quene.poll();
            System.out.println(poll.toString());
            int node = poll.intValue();
            for (int i = 0; i < adj[node].size(); i++) {
                Integer next = adj[node].get(i);
                if (!set.contains(next)) {
                    set.add(next);
                    quene.add(next);
                }
            }
        }


    }


    public static void main(String[] args) {
//        输入：n = 3, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2
//        输出：true
//        解释：存在由顶点 0 到顶点 2 的路径:
//        - 0 → 1 → 2
//                - 0 → 2

        int n = 3;
        int[][] edges = new int[][]{{0,1},{1,2},{2,0}};

        List<Integer>[] adj = new List[n];
        for (int i = 0; i < n; i++) {
            adj[i] = new ArrayList<Integer>();
        }
        for (int[] edge : edges) {
            int x = edge[0], y = edge[1];
            adj[x].add(y);
            adj[y].add(x);
        }


        LeetCode1971_2 leetCode1971_2 = new LeetCode1971_2();
//        leetCode1971_2.bfs(n,edges);

        System.out.println("==================");

//        n = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], source = 0, destination = 5

        int n2 = 6;
        int[][] edges2 = new int[][]{{0,1},{0,2},{3,5},{5,4},{4,3}};

        leetCode1971_2.bfs(n2,edges2);
    }


}
